class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0
        n = str(n)
        return self.search(n, len(n) - 1)

    def search(self, n: str, deepth: int):
        if len(n) == 1:
            return int(n != "0")
        if n[0] == "0":
            return self.search(n[1:], deepth - 1)
        elif n[0] != "1":
            return 10 ** (deepth - 1) * deepth * int(n[0]) + 10 ** deepth + self.search(n[1:], deepth - 1)
        else:
            return 10 ** (deepth - 1) * deepth + int(n[1:]) + 1 + self.search(n[1:], deepth - 1)


def count1(n):
    res = 0
    for i in range(1, n):
        res += str(i).count("1")
    return res


# print(count1(100))  # 20
# print(count1(1000))  # 300
# print(count1(10000))  # 4000

a = Solution()
print(a.countDigitOne(18))  # 11
print(a.countDigitOne(13))  # 6
print(a.countDigitOne(11))  # 4
print(a.countDigitOne(10))  # 2
print(a.countDigitOne(21))  # 13
print(a.countDigitOne(22))  # 13
print(a.countDigitOne(4125))  #
print(a.countDigitOne(100))  # 21
print(a.countDigitOne(101))  # 23
